package com.wngbms.algo;

import java.util.Objects;

public class _06_LinkedList {

    private Node head = null;

    public Node findByValue(int value) {
        if (head == null) {
            return null;
        }

        Node tmp = head;
        do {
            if (tmp.getData() == value) {
                return tmp;
            }
        } while ((tmp = tmp.next) != null);

        return null;
    }

    public Node findByValue2(int value) {
        Node tmp = head;
        while (tmp != null && tmp.data != value) {
            tmp = tmp.next;
        }
        return tmp;
    }

    public Node findByIndex(int index) {
        Node tmp = head;
        int pos = 0;
        /**
         * 链表为空 / 链表长度为1 / 长度为2 / 长度为 无穷
         * index -1 0 1 2 ...
         */
        while (pos < index && tmp != null) {
            tmp = tmp.next;
            pos++;
        }
        return tmp;
    }

    /**
     * 无头节点
     * 
     * @param value
     */
    public void insertToHead(int value) {
        /*
         * if (head == null) {
         * Node node = new Node(value, null);
         * head = node;
         * return;
         * }
         * 
         * Node tmp = head;
         * Node node = new Node(value, tmp);
         * head = node;
         */
        insertToHead(new Node(value, null));
    }

    public void insertToHead(Node node) {
        if (head == null) {
            head = node;
            return;
        }

        node.next = head;
        head = node;
    }

    public void insertTail(int value) {
        insertTail(new Node(value, null));
    }

    public void insertTail(Node node) {
        if (head == null) {
            head = node;
            return;
        }

        Node tail = head;
        while (tail.next != null) {
            tail = tail.next;
        }

        tail.next = node;
    }

    public void insertAfter(Node p, int value) {
        insertAfter(p, new Node(value, null));
    }

    public void insertAfter(Node p, Node newNode) {
        if (p == null || newNode == null) {
            return;
        }

        newNode.next = p.next;
        p.next = newNode;
    }

    public void insertBefore(Node p, int value) {
        insertBefore(p, new Node(value, null));
    }

    public void insertBefore(Node p, Node newNode) {
        if (p == null || newNode == null) {
            return;
        }

        if (p == head) {
            insertToHead(newNode);
            return;
        }

        Node tmp = head;
        while (tmp != null && tmp.next != p) {
            tmp = tmp.next;
        }

        if (tmp == null) {
            return;
        }

        insertAfter(tmp, newNode);
    }

    public void deleteByNode(Node p) {
        if (p == null || head == null) {
            return;
        }

        if (p == head) {
            head = head.next;
            return;
        }

        Node tmp = head;
        while (tmp != null && tmp.next != p) {
            tmp = tmp.next;
        }

        if (tmp == null) {
            return;
        }

        tmp.next = tmp.next.next;
    }

    public void deleteByValue(int value) {
        if (head == null) {
            return;
        }

        /*
         * Node tmp = head;
         * while(tmp != null && tmp.data != value) {
         * tmp = tmp.next;
         * }
         * 
         * if (tmp == null) {
         * return;
         * }
         * 
         * deleteByNode(tmp);
         */

        Node tmp = head;
        Node pre = null; // tip
        while (tmp != null && tmp.data != value) {
            pre = tmp;
            tmp = tmp.next;
        }

        if (tmp == null) {
            return;
        }

        if (pre == null) {
            head = head.next;
        } else {
            pre.next = tmp.next;
        }

    }

    public void printAll() {
        Node tmp = head;
        while (tmp != null) {
            System.out.print(tmp.data + " ");
            tmp = tmp.next;
        }
        System.out.println();
    }

    public static class Node {
        private int data;
        private Node next;

        public Node(int data, Node next) {
            this.data = data;
            this.next = next;
        }

        public int getData() {
            return data;
        }
    }

    public boolean TFResult(Node left, Node right) {
        if (left == null || right == null) {
            return false;
        }

        while (left != null && right != null) {
            if (Objects.equals(left.data, right.data)) {
                left = left.next;
                right = right.next;
            } else {
                return false;
            }
        }

        return true;
    }

    /**
     * 判断是否为回文字符串
     */
    public void palindrome() {
        if (head == null) {
            return;
        }

        Node q = head, p = head;        
        while(q.next != null && q.next.next != null) {
            q = q.next.next;
            p = p.next;
        }

        p.next = inverseLinkList(p.next);
        printAll();
        System.out.println(TFResult(head, p.next));
    }

    public Node inverseLinkList(Node p) {
        if (p == null) {
            return null;
        }

        Node pn = p.next;
        Node r = p;
        r.next = null;

        while (pn != null) {
            p = pn;
            pn = p.next;
            p.next = r;
            r = p;
        }

        return r;
    }

    public static void main(String[] args) {
        _06_LinkedList list = new _06_LinkedList();
        // int data[] = {1};
        // int data[] = {1,2};
        // int data[] = {1,2,3,1};
        // int data[] = {1,2,5};
        // int data[] = {1,2,2,1};
        // int data[] = {1,2,5,2,1};
        // int data[] = { 1, 2, 5, 3, 7, 9 };
        int data[] = { 1, 2, 3, 4, 3, 2, 1 };
        // int data[] = { 2, 2, 3, 4, 4, 3, 2, 2 };

        for (int i = 0; i < data.length; i++) {
            // list.insertTail(data[i]);
            list.insertToHead(data[i]);
        }

        // list.insertAfter(list.head, 66);
        // list.insertBefore(list.head, 77);
        // list.insertAfter(list.findByValue2(3), 33);
        // list.insertAfter(list.findByIndex(0), 888);
        // list.deleteByValue(3);
        // list.deleteByNode(list.head);

        System.out.println("print:");
        list.printAll();

        // list.head = list.inverseLinkList(list.head);
        // list.printAll();

        // list.head.next = list.inverseLinkList(list.head.next);
        // list.printAll();

        list.palindrome();
    }
}
